﻿//#include <iostream>
//#include <cstring>
//using namespace std;
//
//int main() {
//    char string[201], str[3][201];
//    int i;
//
//    for (i = 0; i <= 2; i++)
//        cin >> str[i];
//
//    if (strlen(str[0]) >= strlen(str[1]) && strlen(str[0]) >= strlen(str[2]))
//        strcpy(string, str[0]);
//    else if (strlen(str[1]) >= strlen(str[0]) && strlen(str[1]) >= strlen(str[2]))
//        strcpy(string, str[1]);
//    else
//        strcpy(string, str[2]);
//
//    cout << string;
//
//    return 0;
//}

//#include<bits/stdc++.h>
//using namespace std;
//int main()
//{
//	string s1 = "abc", s2 = "defgh";
//	s1 = s2;
//	cout << s1;
//	return 0;
//}
// 
//class Solution {
//public:
//    vector<int> twoSum(vector<int>& price, int target)
//    {
//        int n = price.size();
//        for (int i = 0; i < n; i++)
//        {
//            for (int j = i + 1; j < n; j++)
//            {
//                if (price[i] + price[j] == target)
//                    return { price[i],price[j] };
//            }
//        }
//        return { -1,-1 };
//    }
//};

//class Solution {
//public:
//    vector<int> twoSum(vector<int>& price, int target)
//    {
//        int cur = 0, dest = price.size() - 1;
//        while (cur < dest)
//        {
//            if (price[cur] + price[dest] > target)
//            {
//                dest--;
//            }
//            else if (price[cur] + price[dest] < target)
//            {
//                cur++;
//            }
//            else
//                return{ price[cur],price[dest] };
//        }
//    }
//    return { -1,-1 };
//};

//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums)
//    {//下标不相等，并且和为0
//        int n = nums.size();
//        for (int i = 0; i < n; i++)
//        {
//            for (int j = i + 1; j < n; j++)
//            {
//                for (int k = j + 1; j < n; j++)
//                {
//                    if (nums[i] + nums[j] + nums[k] == 0)
//                        return { nums[i],nums[j],nums[k] };
//                }
//            }
//        }
//
//    }
//};

//先排序，然后固定一个数，用双指针，注意可以优化一下，只要固定的大于0，就跳出，因为固定的都大于0
//那么后面两个数加起来不可能为负数
//开始循环，只要两个指针之间还有元素，就求和，令target=-固定值，如果大右边减，小就左边加，等于就返回
//最后开始去重，为什么有重复，因为可能两个之间的数是相等的，那么我们就循环判断
//如果左边相等就++，右边相等就--，最后对固定的数i进行去重

//class Solution {
//public:
//    vector<int> twoSum(vector<int>& nums, int target) {
//        int n = nums.size();
//        for (int i = 0; i < n; i++) { // 第⼀层循环从前往后列举第⼀个数
//            for (int j = i + 1; j < n; j++) { // 第⼆层循环从 i 位置之后列举第⼆个
//                数
//                    if (nums[i] + nums[j] == target) // 两个数的和等于⽬标值，说明我们
//                        已经找到结果了
//                        return { nums[i], nums[j] };
//            }
//        }
//        return { -1, -1 };
//    }
//};

//class Solution
//{
//public:
//    vector<vector<int>> fourSum(vector<int>& nums, int target)
//    {
//        vector<vector<int>> ret;
//        // 1. 排序
//        sort(nums.begin(), nums.end());
//        // 2. 利⽤双指针解决问题
//        int n = nums.size();
//        for (int i = 0; i < n; ) // 固定数 a
//        {
//            // 利⽤ 三数之和
//            for (int j = i + 1; j < n; ) // 固定数 b
//            {
//                // 双指针
//                int left = j + 1, right = n - 1;
//                long long aim = (long long)target - nums[i] - nums[j];
//                while (left < right)
//                {
//                    int sum = nums[left] + nums[right];
//                    if (sum < aim) left++;
//                    else if (sum > aim) right--;
//                    else
//                    {
//                        ret.push_back({ nums[i], nums[j], nums[left++],
//                       nums[right--] });
//                        // 去重⼀
//                        while (left < right && nums[left] == nums[left - 1])
//                            left++;
//                        while (left < right && nums[right] == nums[right + 1])
//                            right--;
//                    }
//                }
//                // 去重⼆
//                j++;
//                while (j < n && nums[j] == nums[j - 1]) j++;
//            }
//            // 去重三
//            i++;
//            while (i < n && nums[i] == nums[i - 1]) i++;
//        }
//        return ret;
//    }
//};

//滑动窗口
//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums)
//    {
//        int n = nums.size(), sum = 0, len = INT_MAX;
//        for (int left = 0, right = 0; right < n; right++)
//        {
//            sum += nums[right];//准备进窗口
//            while (sum >= target)
//            {
//                len = min = (len, right - left + 1)//更新
//                    sum -= nums[left++];
//            }
//        }
//        return len == INT_MAX ? 0 : len;
//    }
//};

//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums) {
//        // 记录结果
//            int ret = INT_MAX;
//        int n = nums.size();
//        // 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]
//        // 由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩
//        // 枚举开始位置
//        for (int start = 0; start < n; start++)
//        {
//            int sum = 0; // 记录从这个位置开始的连续数组的和
//            // 寻找结束位置
//            for (int end = start; end < n; end++)
//            {
//                sum += nums[end]; // 将当前位置加上
//
//                if (sum >= target) // 当这段区间内的和满⾜条件时
//                {
//                    // 更新结果，start 开头的最短区间已经找到
//                    ret = min(ret, end - start + 1);
//                    break;
//                }
//            }
//        }
//        // 返回最后结果
//        return ret == INT_MAX ? 0 : ret;
//    }
//};

//void init() 
//{
//    for (int i = 0; i < SIZE; i++) 
//    {
//        array[i] = 0;
//    }
//}
//void print()
//{
//    for (int i = 0; i < SIZE; i++)
//    {
//        printf("%d ", array[i]);
//    }
//    printf("\n");
//}
//void reverse() {
//    int start = 0;
//    int end = SIZE - 1;
//    int temp;
//
//    while (start < end) {
//        temp = array[start];
//        array[start] = array[end];
//        array[end] = temp;
//
//        start++;
//        end--;
//    }
//}

//#include<bits/stdc++.h>
//using namespace std;
//struct stu1 {
//    int x;
//    int* y;
//}*p;
//int dt[4] = {10, 20, 30, 40};
//struct stu a[4] = { 50, &dt[0], 60 ,&dt[1], 70,&dt[2],80, &dt[3] };
//int main()
//{
//    p = a;
//    printf("%d,", ++p->x);
//    printf("%d,"(++p)->x);
//    printf("%d", ++(*p->y));
//    return 0;
//}
//长度最小的子数组
//先来个暴力，从第一个元素开始固定，然后每个元素从当前元素开始，求和，判断是否进窗口，进了的话更新
//长度，并且出窗口，怎么出？
//class Solution {
//public:
//    int lengthOfLongestSubstring(string s)
//    {
//        int n = s.size();
//        for (int left = 0, right = 0; right < n;right++)
//        {
//            int sum = 0;
//            sum += s[right];
//            while(sum>=target)
//        }
//    }
//};

//class Solution {
//public:
//    int lengthOfLongestSubstring(string s) {
//        int ret = 0; // 记录结果
//        int n = s.length();
//        // 1. 枚举从不同位置开始的最⻓重复⼦串
//        // 枚举起始位置
//        for (int i = 0; i < n; i++)
//        {// 创建⼀个哈希表，统计频次
//            int hash[128] = { 0 };
//
//            // 寻找结束为⽌
//            for (int j = i; j < n; j++)
//            {
//                hash[s[j]]++; // 统计字符出现的频次
//                if (hash[s[j]] > 1) // 如果出现重复的
//                    break;
//
//                // 如果没有重复，就更新 ret
//                ret = max(ret, j - i + 1);
//            }
//        }
//        // 2. 返回结果
//        return ret;
//    }
//};

//class Solution {
//public:
//    int lengthOfLongestSubstring(string s)
//    {
//        //暴力,从一个元素枚举，从一个元素判断，
//        int n = s.size(), ret = 0;
//        for (int i = 0; i < n; i++)
//        {
//            int hash[128] = { 0 };
//            for (int j = i; j < n; j++)
//            {
//
//                hash[s[j]]++;
//                if (hash[j[s[j]] > 1)//进窗口
//                {
//                    break;
//                }
//                else
//                {
//                    ret = max(ret, j - i + 1);
//                }
//            }
//
//        }
//        return ret;
//    }
//};


//class Solution
//{
//public:
//    int longestOnes(vector<int>& nums, int k)
//    {
//        int ret = 0;
//        for (int left = 0, right = 0, zero = 0; right < nums.size(); right++)
//        {
//            if (nums[right] == 0) zero++; // 进窗⼝
//            while (zero > k) // 判断
//                if (nums[left++] == 0) zero--; // 出窗⼝
//            ret = max(ret, right - left + 1); // 更新结果
//        }
//        return ret;
//    }
//}


//#include<stdio.h>
//#include<math.h>  
///* #include<math.h> 应为要实现指数和开根所以分别要使
//   用pow函数和sqrt函数    pow(变量,指数)          sqrt(变量)
//*/
//int main()
//{
//    double a, b, c, deta;     //应为有小数，为了方便全部定义为双精度 
//    double x1, x2;
//    scanf("%lf %lf %lf", &a, &b, &c);
//    deta = pow(b, 2) - 4 * a * c;      //计算判断式的值 
//    if (deta > 0)         //deta大于0 
//    {
//        x1 = (-b + sqrt(deta)) / 2 * a;
//        x2 = (-b - sqrt(deta)) / 2 * a;
//        printf("x1=%.3lf x2=%.3lf\n", x1, x2);
//    }
//    else if (deta == 0)          //deta等于0 
//    {
//        x1 = (-b) / (2 * a);
//        x2 = (-b) / (2 * a);
//        printf("x1=%.3lf x2=%.3lf\n", x1, x2);
//    }
//    else      //deta小于0 
//    {
//        double m, n;    //因为是共轭复根，定义两个变量 
//        m = (-b) / (2 * a);
//        n = sqrt(-deta) / (2 * a);
//        printf("x1=%.3lf+%.3lfi x2=%.3lf-%.3lfi\n", m, n, m, n);
//    }
//    return 0;
//}
//
//




















//#include<bits/stdc++.h>
//using namespace std;
//int main()
//{
//    string s;
//    cin >> s;
//    reverse(s.begin(), s.end());
//    cout << s;
//
//    return 0;
//}
//反转字符串//puts遇到\0停，不放\0会很烫
//#include<stdio.h>
//#include<string.h>
//
//int exchange(char a[], char b[])
//{
//    int i, l, j = 0;
//    l = strlen(a);
//    for (i = l - 1; i >= 0; i--) {
//        b[j] = a[i];
//        j++;
//    }
//    b[j] = '\0';       //给末尾加上结束符。
//    return 0;
//}
//
//int main()
//{
//    char a[1000], b[1000];
//    gets(a);
//    exchange(a, b);
//    puts(b);
//    return 0;
//}

//一个指针指向一个字符串末尾，一个指针指向开头，接着一个一个赋值
//连接两个字符串，思路就是s接受的是str1的地址，t接受的是str2的地址，那么要把t赋值到s的末端，只需
//指向str1的指针s自增到/0的位置，然后把str2赋给str1，同时两种指针向后移动
//char* str_cat(char* s, char* t)
//{
//	char* p = s;
//	while (*s != '\0')
//	{
//		s++;
//	}
//	//出循环的时候s指向的是/0位置
//	//开始把str2赋给str1；
//	int i = 0;
//	while (*(t+i) != '\0')
//	{
//		*(s+i) = *(t+i);
//		i++;
//	}
//	*(s + i) = '\0';
//	return p;
//}
//先是主对角线，就是从左上到右下的那条线，我们可以直观的发现它的行列坐标是相等，所以在C语言中的表现形式就是i == j；
//
//然后是副对角线，从右上到左下，通过观察我们可以发现在3 * 3矩阵中，副对角线上的元素行列坐标相加是等于4，但是这里要注意的是：在C语言中数组的下标是从0开始的。所以表现形式为：i + j == 2。
//
//
//#include<stdio.h>
//int main()
//{
//    int a[3][3];
//    int i, j, sum1 = 0, sum2 = 0;
//    for (i = 0; i < 3; i++) {
//        for (j = 0; j < 3; j++) {
//            scanf("%d", &a[i][j]);
//        }
//    }
//    for (i = 0; i < 3; i++) {
//        for (j = 0; j < 3; j++) {
//            if (i == j)
//                sum1 += a[i][j];
//            if (i + j == 2)
//                sum2 += a[i][j];
//        }
//    }
//    printf("%d %d\n", sum1, sum2);
//    return 0;
//}
//先找到需要插入的位置，然后从后往前插入，因为这样不会覆盖
// 首先是输入只含有9个元素的数组a[10]，用for循环依次输入。接着输入插入的数字m，将m与数组元素比较。

//1、当m <= a[0]时，记录t = 0;
//
//2、当m >= a[8]时，记录9；
//
//3、当a[i] <= x <= a[i + 1]时，记录x应该插入的位置t = i + 1。
//
但是插入m之前要把元素往后移位，从后往前直到位置t，最后把m赋值给a[t]，用for循环输出排好的a[10]。
注意事项 : 1、找插入位置时注意break退出遍历循环, 不然就会出错误；

2、移位从后往前，不然从前往后会使数据丢失。
//#include<stdio.h>
//int main()
//{
//    int a[10], i, m, t;
//    for (i = 0; i < 9; i++)
//    {
//        scanf("%d", &a[i]);
//    }
//    a[9] = 0;
//    scanf("%d", &m);
//    if (m <= a[0])
//        t = 0;
//    if (m >= a[8])
//        t = 9;
//    for (i = 0; i < 9; i++)
//    {
//        if (m >= a[i] && m <= a[i + 1])
//        {
//            t = i + 1;
//            break;
//        }
//    }
//    for (i = 9; i > t; i--)
//    {
//        a[i] = a[i - 1];
//    }
//    a[t] = m;
//    for (i = 0; i < 10; i++)
//    {
//        printf("%d", a[i]);
//        printf("\n");
//    }
//    return 0;
//}
//重放
//#include<stdio.h>
//int main()
//{
//    int arr[100] = { 0 };
//    int n = 0;
//    int i = 0;
//    int j = 0;
//    scanf("%d", &n);
//    while (i < n)
//    {
//        scanf("%d", &arr[i]);
//        i++;
//    }
//    for (i = n - 1, j = 0; i >= 0; i--, j++)//重放，注意循环条件****
//    {
//        int temp = 0;
//        temp = arr[i];
//        arr[i] = arr[j];
//        arr[j] = temp;
//    }
//    for (j = 0; j < n; j++)
//    {
//        printf("%d", arr[j]);
//        if (j < n - 1)
//        {
//            printf(" ");
//        }
//    }
//    return 0;
//}


//C++
//#include <iostream>
//using namespace std;
//int main()
//{
//    int L, M, x, y, a[10001];
//    cin >> L >> M;
//    for (int i = 0; i <= L; i++)  //先将数组全赋值为1 
//        a[i] = 1;
//    for (int i = 0; i < M; i++)
//    {
//        cin >> x >> y;      //[x,y]为区域区间
//        for (int j = x; j <= y; j++)  //将区域区间内的值赋为0
//            a[j] = 0;
//    }
//    int sum = 0;
//    for (int i = 0; i <= L; i++)
//    {
//        if (a[i] == 1)     //如果数组元素值是1 则计数加1 
//            sum++;
//    }
//    cout << sum;
//    return 0;
//}
//摘苹果
//#include <stdio.h>
//int main() {
//    int a[11], i, n, cnt = 0;
//    for (i = 0; i < 10; i++) scanf("%d", &a[i]);
//    scanf("%d", &n);
//    for (i = 0; i < 10; i++) {
//        if (n + 30 >= a[i])
//            cnt++;
//    }
//    printf("%d", cnt);
//}

//#include<bits/stdc++.h>
//using namespace std;
//int main()
//{
//	int n;
//	cin >> n;
//	vector<int>arr(n);
//	for (int i = 0; i < n; i++)
//	{
//		cin >> arr[i];
//	}
//	sort(arr.begin(), arr.end());
//	int j = 0;
//	vector<int>arr1(n-1);
//	for (int i = 0; i < n-1; i++)
//	{
//		arr1[j++] = abs(arr[i] - arr[i + 1]);
//	}
//	int flag = 1, k = 0;
//	sort(arr1.begin(), arr1.end());
//	for (int i = 0; i < arr1.size(); i++)
//	{
//		if (++k != arr1[i])
//		{
//			flag = 0;
//			break;
//		}
//	}
//	if (flag == 0)
//		cout << "Not jolly";
//	else
//		cout << "Jolly";
//
//	return 0;
//}


//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//int main()
//{
//    int n;
//    cin >> n;
//    vector<int> arr(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> arr[i];
//    }
//    vector<int> diff(n - 1);
//    for (int i = 0; i < n - 1; i++)
//    {
//        diff[i] = abs(arr[i] - arr[i + 1]);
//    }
//    sort(diff.begin(), diff.end());
//    bool isJolly = true;
//    for (int i = 0; i < n - 1; i++)
//    {
//        if (diff[i] != i + 1)
//        {
//            isJolly = false;
//            break;
//        }
//    }
//    if (isJolly)
//    {
//        cout << "Jolly";
//    }
//    else
//    {
//        cout << "Not jolly";
//    }
//    return 0;
//}
